Related art of group signature which use bilinear mapping includes a group signature described in Dan Boneh, Xavier Boyen: “Short Group Signature: Advances in Cryptology—CRYPTO 2004,” Lecture Notes in Computer Science 3152, pp. 41-55, 2004, Springer. The outline of this group signature will be described below.
Let a randomly selected unknown γ of a field Z/pZ with p being a prime number be the group secret key.
Let a letter string which describes: the prime number p; group 1, group 2 and group T which are of order number p; a bilinear map e from group 1 and group 2 to group T; an isomorphic map φ from group 2 to group 1; and a hash function Hash for mapping a letter string to field (Z/pZ), a generator G2 of group 2, a generator G1 of group 1 where φ(G2=G1, a randomly selected unknown H of group 1, and W=[γ]G2 be the group public key.
Where, W is the point of γ times G2.
Further, let randomly selected two points ξ1, ξ2 on field Z/pZ be the tracking secret key.
Let randomly selected two points on group 2 in which [ξ1]U=[ξ2]V=H be the tracking public key. And let a randomly selected point x on field Z/pZ be the member secret key.
Further, Let a randomly selected point y on field Z/pZ and A where A=[1/(γ+y)]([1−x]G1) be the member certificate.
Hereinafter, the group signing device will be described.
The group signing device is input with a message to be signed, a group public key, a tracking public key, a member secret key, a member certificate, and a random number.
The group signing device randomly selects points α and β on Z/pZ using an input random number and generates encrypted text, T1=[α]U, T2=[β]V, T3=[α+β]H.
The group signing device further randomly selects points α′, β′, δ′1, δ′2, and y′ on Z/pZ using an input random number, and generates a commitment, R1=[α′]U, R2=[β′]V, R3=e(T3,G2)^(x′)·e(H,W)^(−α′−β′)·e(H,G2)^(−δ′1−δ′2)·e(H,G2)^(y′), R4=[x′]T1−[¥delta′1]U, R5=[x′]T2−[¥delta′2]V, where symbol [^] means a power modulo operation.
The group signing device generates a hash value of a group public key, a tracking public key, a message, and U,V,T1,T2,T3,R1,R2,R3,R4,R5 to use as challenge value c.
The group signing device generates a response, sα=α′+cα, sβ=β′+cβ, sx=x′+cx, sδ1=δ′1+cxα, sδ2=cxβ, sy=y′+xy.
The group signature outputs T1,T2,T3,c,sα,sβ,sx,sδ1,sδ2,sy as the group signature for message m.
Hereinafter, the group-signature verifying device will be described.
The group-signature verifying device is input with a signed message, a group public key, and a tracking public key.
The group-signature verifying device generates R1=[sα]U−[c]T1, R2=[sβ]V−[c]T2, R3=e(T3,G2)^(sx)·e(H,W)^(−sα−sβ)·e(H,G2)^(−sδ1−sδ2)·e(H,G2)^(sy)(e(G1,G2)/e(T3,W))^(c), R4=[sx]T1−[sδ1]U, R5=[sx]T2−[sδ2]U, and generates a hash value of the group public key, the tracking public key, the signed message and U,V,T1,T2,T3,R1,R2,R3,R4,R5 to verify if this corresponds to challenge value c. If there is a correspondence, it is judged that the group signature is valid and, if not, invalid.